//class Solution {
//public:
//    int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
//    int m, n;
//    bool vis[10][10] = { 0 };
//    bool exist(vector<vector<char>>& board, string word) {
//        m = board.size(), n = board[0].size();
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (board[i][j] == word[0])
//                {
//                    vis[i][j] = true;
//                    if (dfs(board, word, i, j, 1)) return true;
//                    vis[i][j] = false;
//                }
//            }
//        }
//        return false;
//    }
//
//    bool dfs(vector<vector<char>>& board, string& word, int i, int j, int pos)
//    {
//        if (pos == word.size()) return true;
//        for (int k = 0; k < 4; k++)
//        {
//            int x = i + dx[k], y = j + dy[k];
//            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && board[x][y] == word[pos])
//            {
//                vis[x][y] = true;
//                if (dfs(board, word, x, y, pos + 1)) return true;
//                vis[x][y] = false;
//            }
//        }
//        return false;
//    }
//};




//class Solution {
//public:
//    int ret = 0;
//    int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
//    int m, n;
//    bool vis[20][20] = { 0 };
//    int getMaximumGold(vector<vector<int>>& grid) {
//        m = grid.size(), n = grid[0].size();
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (grid[i][j])
//                {
//                    vis[i][j] = true;
//                    dfs(grid, i, j, grid[i][j]);
//                    vis[i][j] = false;
//                }
//            }
//        }
//        return ret;
//    }
//
//    void dfs(vector<vector<int>>& grid, int i, int j, int prevsum)
//    {
//        ret = max(ret, prevsum);
//        for (int k = 0; k < 4; k++)
//        {
//            int x = i + dx[k], y = j + dy[k];
//            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y])
//            {
//                vis[x][y] = true;
//                dfs(grid, x, y, prevsum + grid[x][y]);
//                vis[x][y] = false;
//            }
//        }
//    }
//};




class Solution {
public:
    int ret = 0, m, n;
    bool vis[21][21];
    int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
    int step, sx, sy;
    int uniquePathsIII(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 1) sx = i, sy = j, vis[i][j] = true;
                else if (grid[i][j] == 0)step++;
        step++;
        dfs(grid, sx, sy, 0);
        return ret;
    }

    void dfs(vector<vector<int>>& grid, int i, int j, int num)
    {
        if (grid[i][j] == 2)
        {
            if (num == step) ret++;
            return;
        }

        for (int k = 0; k < 4; k++)
        {
            int x = dx[k] + i, y = dy[k] + j;
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] != -1)
            {
                vis[x][y] = true;
                dfs(grid, x, y, num + 1);
                vis[x][y] = false;
            }
        }
    }

};